package cn.lishiyuan.algorithm.sort;


import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;

/**
 * 基数排序
 * <br>
 * 基数排序的思路是，数据的高位大小可以决定大小的情况下，对每一位数据从低到高进行稳定排序。
 */
public class RadixSort{

    private static class Item<T>  implements Comparable<Item<T>>{
        T value;
        int index;
        Integer[] radix;

        @Override
        public int compareTo(Item<T> o) {
            if(index != o.index){
                throw new IllegalStateException("位置不一致");
            }
            return radix[index].compareTo(o.radix[index]);
        }
    }


    public <T extends Comparable<T>> List<T> sort(List<T> data,Function<T, Integer[]> slip) {
        if (data == null || data.size() <= 1){
            return data;
        }

        // 进行分割
        List<Item<T>> result = new ArrayList<>(data.size());
        for (T d : data) {
            Item<T> item = new Item<>();
            Integer[] indexArr = slip.apply(d);
            item.index = indexArr.length - 1;
            item.radix = indexArr;
            item.value = d;
            result.add(item);
        }

        // 按位进行排序
        int n = result.get(0).index;

        LeeSort sort = new MergeSort();

        for (int i = 0; i <= n; i++){
            sort.sort(result);
            for (Item<T> item : result) {
                item.index--;
            }
        }

        return result.stream().map(d -> d.value).toList();
    }

}